package practice.tmp;

//https://leetcode.cn/problems/sort-list/solutions/1713438/by-nuo-nuo-zi-4-xrok/
public class Solution148 {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode h1 = new ListNode();
        ListNode h2 = new ListNode();
        ListNode h3 = new ListNode();
        ListNode t1 = h1;
        ListNode t2 = h2;
        ListNode t3 = h3;
        int pivot = getMid(head).val;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            if (cur.val < pivot) {
                cur.next = null;
                t1.next = cur;
                t1 = t1.next;
            } else if (cur.val == pivot) {
                cur.next = null;
                t2.next = cur;
                t2 = t2.next;
            } else {
                cur.next = null;
                t3.next = cur;
                t3 = t3.next;
            }
            cur = tmp;
        }
        h1 = sortList(h1.next);
        h3 = sortList(h3.next);
        h2 = h2.next;
        t2.next = h3;
        if (h1 == null) {
            return h2;
        } else {
            t1 = h1;
            while (t1.next != null) t1 = t1.next;
            t1.next = h2;
            return h1;
        }
    }

    public ListNode getMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
